package com.harvey.study.data.structure.datastructure.tree;

/**
 * 
 * date: 2021-05-03
 * desc: 通过链表实现树形结构
 */
public class LinkedTree<T> {
    private TreeNode<T> root;

    public LinkedTree() {

    }

    public LinkedTree(T data) {
        this.root = new TreeNode<T>(data);
    }

    public boolean insertLeft(T data,TreeNode<T> parent){
        if(parent == null){
            return false;
        }
        TreeNode<T> child = new TreeNode<T>(data);
        if(parent.getLchild() == null){
            parent.setLchild(child);
        }else{
            TreeNode<T> lChild = parent.getLchild();
            child.setLchild(lChild);
            parent.setLchild(child);
        }
        return true;
    }

    public boolean insertRight(T data,TreeNode<T> parent){
        if(parent == null){
            return false;
        }
        TreeNode<T> child = new TreeNode<T>(data);
        if(parent.getRchild() == null){
            parent.setRchild(child);
        }else{
            TreeNode<T> lChild = parent.getRchild();
            child.setRchild(lChild);
            parent.setRchild(child);
        }
        return true;
    }

    public boolean deleteLeft(TreeNode<T> parent){
        if(parent == null){
            return false;
        }
        parent.setLchild(null);
        return true;
    }

    public boolean deleteRight(TreeNode<T> parent){
        if(parent == null){
            return false;
        }
        parent.setRchild(null);
        return true;
    }

    public boolean search(T data){
        return true;
    }

    public int getHeight(TreeNode<T> parent){
        if(parent == null){
            return 0;
        }
        int left = getHeight(parent.getLchild());
        int right = getHeight(parent.getRchild());
        int max = left>right ? left : right;
        return max+1;

    }

    public void printNode(TreeNode<T> parent){
        System.out.println(parent.getData());
    }

    /**
     * 先序遍历
     */
    public void preOrder(TreeNode<T> parent){
        if(parent == null){
            return;
        }
        printNode(parent);
        preOrder(parent.getLchild());
        preOrder(parent.getRchild());
    }

    /**
     * 后序遍历
     */
    public void postOrder(TreeNode<T> parent){
        if(parent == null){
            return;
        }
        postOrder(parent.getLchild());
        postOrder(parent.getRchild());
        printNode(parent);

    }

    /**
     * 中序遍历
     */
    public void inOrder(TreeNode<T> parent){
        if(parent == null){
            return;
        }
        inOrder(parent.getLchild());
        printNode(parent);
        inOrder(parent.getRchild());
    }

    
    public static void main(String[] args) {
        TreeNode<String> a = new TreeNode<String>("A");

        LinkedTree<String> linkedlist = new LinkedTree<String>(a.getData());


        linkedlist.insertLeft("B",linkedlist.root);
        linkedlist.insertRight("C",linkedlist.root);


        linkedlist.insertLeft("D",linkedlist.root.getLchild());
        linkedlist.insertRight("E",linkedlist.root.getLchild());

        linkedlist.insertLeft("F",linkedlist.root.getRchild());

        // linkedlist.preOrder(linkedlist.root);

        // linkedlist.inOrder(linkedlist.root);

        linkedlist.postOrder(linkedlist.root);

        System.out.println(linkedlist.getHeight(linkedlist.root));

    }
    
}
